1. Field of the Invention
The present invention relates to integrated circuits, and, in particular, to high-density programmable logic devices (PLDs), such as field programmable gate arrays (FPGAs).
2. Description of the Related Art
One of the primary problems in FPGA architectures is the design of structures connecting routing resources to logic cell inputs. These structures must provide switching for signals connecting to the input pins of the look-up tables (LUTs), flip-flops (FFs), and other logic elements within an FPGA logic cell (typically, but not necessarily, within the programmable function unit (PFU) of the logic cell). Typically, the number of pins on the logic elements is different from the number of routing resources available.
The connections between routing resources and logic cell inputs is generally recognized as one of the keys to successful FPGA architectures. Architectures with too many of these connections tend to be slower and use more silicon area. Providing unlimited access to logic cells with large numbers of input pins can lead to congestion in the global routing. Such designs can require an excessive number of global routing tracks. On the other hand, architectures that have too few of these connections can suffer routability problems where the density of logic elements is high or require underutilization of logic elements. Either of these will result in a reduction in the amount of user-defined logic that can be implemented in a given device, which is inefficient.
To address these problems, some FPGA architectures have implemented input sharing between logic cell input pins. Input sharing means that two or more different logic cell input pins are constrained to use the same user-defined signal. In existing FPGAs, this constraint is fixed. That is, two pins that have a shared input always share that input, independent of the user-defined programming. Such input sharing reduces the flexibility of the connections between routing and logic element input pins, which, in turn, typically reduces the average amount of logic that can be implemented by the logic elements.
FIGS. 1 and 2 show examples in which the PFU of a logic cell contains three 4-input look-up tables (LUT1, LUT2, and LUT3). The total number of input pins of the PFU is m, the number of routing resources that could possibly be connected to the input pins is n, and the maximum number of distinct user-defined signals that can be connected to the LUT inputs is k. The input structure comprises a switch and a set of interconnections. The switch is multiport, typically implemented as pass transistors, multiplexors, antifuses, fuses, etc.
FIG. 1 shows a prior-art architecture in which the input structure has a distinct connection for every logic element input pin. This fixed input structure involves no sharing of input signals between any of the LUT input pins. In this case, the value of k always equals the value of m (i.e., in this example, 12). This provides the maximum amount of flexibility for packing logic into the LUTs, since none of the LUTs needs to share an input signal with any other LUT. The costs of such a connection scheme, however, quickly grow prohibitive as the number of input pins m gets large. This is due to the fact that the programmable routing used to route the logic elements together must always be able to handle the worst case where every input pin m has a distinct signal on it. In addition, speed performance will suffer, as the loading grows quickly due to the need to provide a complete set of connections. Various schemes have been used in existing FPGAs in the design of this input structure to connect the n routing signals to the k input signals. One is a fully populated switch, where any of the n inputs to the switch can connect to any of the k outputs, while maintaining the fact that k is equal to the number of logic element input pins m.
FIG. 2 shows a prior-art architecture having a fixed input structure that involves the use of input sharing, where two or more logic elements are constrained to use the same distinct input signal on one or more of their pins. In this case, the number of distinct input signals k is fixed to be less than the number of logic element inputs m. For the particular example shown, each pair of adjacent LUTs shares one input. Thus, k is equal to 10, while m remains at 12. This reduces the amount of logic, but also reduces the amount of programmable routing required to connect the logic elements together since the maximum possible distinct input signals k will always be less than the number of input pins m. In the example of FIG. 2, if the logic to be implemented does not involve LUTs that can share an input, the PFU cannot be fully utilized. Other schemes have used less than fully populated switches, sometimes combined with input sharing. All of the prior-art architectures that rely on input sharing have a fixed amount of input sharing, where every instance of the logic cell forces the same sharing scheme between internal logic elements, such as LUTs, of the input signals, no matter what the requirements demanded by the user's circuitry of a particular logic element might be.